package main
import (
	"time"
	"fmt"
	"container/list"
	"math"
)

const M uint64 = 600851475143
//const M uint64 = 13195
//const M int = 1000

var primesList *list.List
var isMultiple bool = false

func init() {
	primesList = list.New()
}

func main() {
	start := time.Now()
	fmt.Println("M = ", M)
	max := math.Sqrt(float64(M))
	max = math.Floor(max)
	N := int(max)
	fmt.Println("N = ", N)
	primesList.PushBack(2)
	primesList.PushBack(3)
	primesList.PushBack(5)
	for i := 6; i < N; i++ {
		if (i % 2 == 0) || (i % 3 == 0) || (i % 5 == 0) {
			continue
		}
		//fmt.Println("Current i = ", i)
		for e := primesList.Front(); e != nil; e = e.Next() {
			if e.Value.(int) <= int(math.Sqrt(float64(N)))  {
				//fmt.Printf("-Gonna compare %v with %v\n", i, e.Value.(int))
				if i % e.Value.(int) != 0 {
					//fmt.Printf("--continuing\n")
					isMultiple = false
					continue
				} else  {
					//fmt.Printf("--getting next i\n")
					isMultiple = true
					break
				} 
			} else {
				isMultiple = false
				break
			}
		}
		if isMultiple == false {
			primesList.PushBack(i)
			fmt.Println("+++Added Prime: ", i)
			isMultiple = false
		}
	}
	fmt.Printf("Prime list till %v:\n", N)
	k := 0
	for e := primesList.Front(); e != nil; e = e.Next() {
		fmt.Printf("|%v", e.Value.(int))
		k++
		if  k % 10 == 0 {
			fmt.Printf("|\n")
		}
	}
	fmt.Printf("|\n")
	fmt.Println("+++prime no: ", k)

	for e := primesList.Front(); e != nil; e = e.Next() {
		if M % uint64(e.Value.(int)) == 0 {
			fmt.Println("found prime multiple: ", uint64(e.Value.(int)))
		}
	}
	stop := time.Now()
	fmt.Println("Execution time: ",  stop.Sub(start))
}




